import collections


class Solution(object):
    def accountsMerge(self, accounts):
        """
        :type accounts: List[List[str]]
        :rtype: List[List[str]]
        """
        n = len(accounts)
        p = [i for i in range(n)]
        d = collections.defaultdict(list)
        e = collections.defaultdict(set)

        def find(x):
            if p[x] == x:
                return x
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx < rooty:
                    p[rooty] = rootx
                else:
                    p[rootx] = rooty

        for i, a in enumerate(accounts):
            for m in a[1:]:
                d[m].append(i)
        for key in d:
            if len(d[key]) >= 2:
                x = d[key][0]
                for y in d[key][1:]:
                    union(x, y)
        for i in range(n):
            index = find(i)
            for m in accounts[i][1:]:
                e[index].add(m)
        out = []
        for index in e:
            name = accounts[index][0]
            email = list(e[index])
            email.sort()
            out.append([name] + email)
        return out


data = Solution()
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"],
            ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
print(data.accountsMerge(accounts))
accounts = [["Gabe", "Gabe0@m.co", "Gabe3@m.co", "Gabe1@m.co"], ["Kevin", "Kevin3@m.co", "Kevin5@m.co", "Kevin0@m.co"],
            ["Ethan", "Ethan5@m.co", "Ethan4@m.co", "Ethan0@m.co"],
            ["Hanzo", "Hanzo3@m.co", "Hanzo1@m.co", "Hanzo0@m.co"], ["Fern", "Fern5@m.co", "Fern1@m.co", "Fern0@m.co"]]
print(data.accountsMerge(accounts))
